package offerbook;

/**
 * 给定n，打印 1- n位数最大值。
 * 如n = 2， 打印 1-99.
 * @date 2020/3/8 21:52
 */
public class Code12_Print1ToMaxN_打印大数 {

    public static void printMax(int n){
        if(n <= 0) return;
        //这里可以用byte表示，也可以用char表示，也可以用bitmap等等
        byte[] nums = new byte[n]; // 0-n-1位总共代表n位。
        while (!incrementAndIsOver(nums)){
            printNum(nums);
        }
    }

    /**
     * 方式1：用数组来处理大数
     * 不足：一个byte能表示 0 -127，在这里只表示了 0-9，浪费空间
     */
    private static boolean incrementAndIsOver(byte[] nums) {
        boolean isOver = false;
        byte over = 0; //是否进位
        //byte小位为数的高位，大位为数的低位
        //如：byte=[1,2,3,4] 代表数1234
        for (int i = nums.length - 1; i >= 0; i--) {
            //第一次循环就是原本的nums[len-1]，即最低位
            int sum = nums[i] + over;
            //数的最低位(数组的最高位置) 要自增
            if(i == nums.length - 1){
                sum ++;
            }
            //进位处理
            if(sum >= 10){
                over = 1;
                sum -= 10;
                //如果来到了最高位还是进位，代表溢出
                if(i == 0) return true;
                nums[i] = (byte) sum;
            }else {
                nums[i] = (byte) sum;
                break;
            }
        }
        return isOver;
    }

    /**
     * 注意打印： 0000123打印123，从数组的最低位(数的最高位)找第一个非0
     */
    private static void printNum(byte[] nums) {
        boolean begin0 = true;
        for (int i = 0; i < nums.length; i++) {
            //begin0 && nums[i]中begin0可以不加，加了优化
            if(begin0 && nums[i] != 0) begin0 = false;
            if(!begin0){
                System.out.print(nums[i]);
            }
        }
        System.out.println();
    }

    /**
     * 方式2：给n，打印 1- n-1个9，其实上就是 1- n-1个9的顺序全排列！
     */
    public static void printMax2(int n){
        if(n <= 0) return;
        byte[] nums = new byte[n];
        //最高位，也就是nums[0]，从0-9控制。
        //以 n = 3为例，第一轮打印0-99，第二轮100-199,....，第十轮打印900-999
        for (int i = 0; i < 10; i++) {
            nums[0] = (byte) i;
            //最高位被占用了，从次高位开始赋值
            doPrint(nums,1);
        }
    }

    private static void doPrint(byte[] nums, int index) {
        //base case，打印
        if(index == nums.length){
            printNum(nums);
            return;
        }
        //从index位开始，从0-9赋值，然后给index+1位。严格的按照顺序.
        for (int i = 0; i < 10; i++) {
            nums[index] = (byte) i;
            doPrint(nums,index+1);
        }
    }

    public static void main(String[] args) {
        printMax2(4);
    }

}
